package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3.5 MB, 在所有 Go 提交中击败了5.31%的用户
 */
func nextGreaterElement(nums1 []int, nums2 []int) []int {

	stk := make([]int, 0)
	q := make([]int, len(nums2))
	for i := len(nums2) - 1; i >= 0; i-- {
		x := nums2[i]
		for len(stk) > 0 && x >= stk[len(stk) - 1] { stk = stk[:len(stk) - 1] }
		if len(stk) == 0 {
			q[i] = -1
		} else {
			q[i] = stk[len(stk) - 1]
		}
		stk = append(stk, x)
	}

	hash := make(map[int]int, 0)
	for i := 0; i < len(nums2); i++ { hash[nums2[i]] = i }

	res := []int{}
	for _, x := range nums1 {
		res = append(res, q[hash[x]])
	}
	return res
}

func main() {

	nums1 := []int{4, 1, 2}
	nums2 := []int{1, 3, 4, 2}
	fmt.Println(nextGreaterElement(nums1, nums2))
}
